/*
 * Created on Jun 24, 2005
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
package clustering.implementations;
import clustering.framework.*;

import org.w3c.dom.Document;
import org.w3c.dom.Node;

import java.util.*;

/**
 * @author Administrator
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class BinaryTreeScorer implements IClusterTreeScorer{
	QNode [] qNodes = null;
    Hashtable htPath = null;
    int sum(int n){
		int s = 0;
		for(int i=0;i<n;i++){
			s += i;
		}
		return s;
	}
	public double ComputeScore(Document xmlTree, double [][] dMatrix){
		int [][] checked = new int[dMatrix.length][dMatrix.length];
		DMElement [] orderedDist = new DMElement[sum(dMatrix.length)];
		for(int k=0;k<sum(dMatrix.length);k++){
			double min_dist = Double.MAX_VALUE;
			int min_i = -1, min_j = -1;
			for(int i=0;i<dMatrix.length;i++){
				for(int j=i+1;j<dMatrix.length;j++){
					if(min_dist > dMatrix[i][j] && checked[i][j]==0){
						min_dist = dMatrix[i][j];
						min_i = i;
						min_j = j;
					}
				}
			}
			orderedDist[k] = new DMElement(min_i,min_j,min_dist);
			checked[min_i][min_j]=1;
		}
		
		Arrays.sort(orderedDist);
		int [] treeDist = new int[orderedDist.length];
		
		qNodes = new QNode[2*dMatrix.length-2];
        ArrayList alQuartets = Quartet.generateFullQuartetList(dMatrix);
        QuartetTree qt = constructFromXmlDocument(xmlTree);
        
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
		for(int i=0;i<treeDist.length;i++){
			DMElement dme = orderedDist[i];
			//ArrayList path = qt.Dijkstra()
			QNode n1 = getNodeByLabel(dme.i);
			QNode n2 = getNodeByLabel(dme.j);
			ArrayList path = qt.Dijkstra(n1,n2,qNodes);
			treeDist[i] = path.size();
			if(max < treeDist[i])max = treeDist[i];
			if(min > treeDist[i])min = treeDist[i];
		}
		double change_count = 0;
		int old_value = -1;
		old_value = treeDist[0];
		for(int i=1;i<treeDist.length;i++){
			int diff = Math.abs(old_value - treeDist[i]);
			change_count += diff * 0.5;
			old_value = treeDist[i];
		}		
		return 1 - ((double)change_count - ((double)max/2 - (double)min/2))/(2*(double)treeDist.length);
		//return 1 - (double)change_count/(double)treeDist.length;
	}
	int node_count;
    QuartetTree constructFromXmlDocument(Document xmlTree){
        QuartetTree qt = new QuartetTree();
        QNode qn = new QNode(-1,null,null,null,-1);
        Node xmlNode = xmlTree.getFirstChild();
        node_count = 0;
        for(int i=0;i<xmlNode.getChildNodes().getLength();i++){
			generateTree(xmlNode.getChildNodes().item(i),qn);
		}
        if(xmlNode.getChildNodes().getLength()==2){
		    QNode n1 = qn.adj[0];
		    QNode n2 = qn.adj[1];
		    n1.adj[0] = n2;
		    n2.adj[0] = n1;
		    qt.root = n1;
		}else{
		    qNodes[node_count++]=qn;
		    qt.root = qn;
		}        
        return qt;
    }
    void generateTree(Node xmlNode, QNode n0){
        String sId = xmlNode.getAttributes().getNamedItem("id").getNodeValue();
		int id = Integer.parseInt(sId);
		QNode qn = new QNode(id,n0,null,null,-1);
		if(n0.adj[0]==null)n0.adj[0]=qn;
		else if(n0.adj[1]==null)n0.adj[1]=qn;
		else n0.adj[2]=qn;
		if(xmlNode.hasChildNodes()){
			for(int i=0;i<xmlNode.getChildNodes().getLength();i++){
				generateTree(xmlNode.getChildNodes().item(i),qn);
			}			
		}
		qNodes[node_count++]=qn;
	}
    QNode getNodeByLabel(int label){
        for(int i=0;i<qNodes.length;i++){
            QNode qn = qNodes[i];
            if(qn.label == label)return qn;
        }
        return null;
    }
}
